package LeetCode;

import java.util.*;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}21:22
 */
public class LeetCode93II {


    public static void main(String[] args) {
        System.out.println(new LeetCode93II().restoreIpAddresses("25525511135").toString());
    }

    public List<String> restoreIpAddresses(String s) {
        List<String> list = new ArrayList<>();
        if (s == null || s.equals("")){
            return list;
        }
        int len = s.length();
        if (len <  4 || len > 12){
            return list;
        }

        Deque<String> path = new LinkedList<>();
        dfs(s,0,0,path,len,list);
        return list;
    }

    public void dfs(String s,int times,int begin,Deque<String> path,int len,List<String> list){
        if (begin == len){
            if (times == 4){
                list.add(String.join(".",path));
                return;
            }
        }

        // 看剩下的位数是否还满足一个合格的IP地址
        if (len - begin < (4 - times) || len - begin > 3 * (4 - times)){
            return;
        }

        for (int i = 0; i < 3; i++){// 这里循环三次 是因为每段最多三个
            if (begin + i >= len){
                break;
            }

            int ipSegment = judgeIpSegment(s,begin,begin + i);
            if (ipSegment != -1) {
                path.add(ipSegment + "");
                dfs(s, times + 1, begin + i + 1, path, len, list);
                path.removeLast();
            }
        }
    }

    public int judgeIpSegment(String s, int begin, int right) {
        int len = right - begin + 1;
        if (len > 1 && s.charAt(begin) == '0'){// IP开头不能为0
            return -1;
        }

        int res = 0;
        for (int i = 0; i < len; i++){
            res = res*10 + (s.charAt(begin + i) - '0');
        }
        if (res > 255){// IP段最大255
            return -1;
        }
        return res;
    }

}
